package offer.day36;

public class No68Second_FetLowestCommonAncestorTreeParent {
    /*
     * 面试题68：最低公共祖先
     * 给出树中的两个节点，求这两个节点的最低公共祖先
     * 题目二：树是普通树，但有指向父节点的指针
     *
     *
     * 思路：两个节点若是在两条路径上，类似于两个链表的第一个公共节点。
     * 由于每个节点的深度最多为logn，所以时间复杂度O(logn)，空间复杂度O(1)
     *
     * */
    public static void main(String[] args) {
        No68Second_FetLowestCommonAncestorTreeParent p =  new No68Second_FetLowestCommonAncestorTreeParent();

        TreeNode root1 = new TreeNode(5);
        TreeNode one = new TreeNode(3);
        TreeNode two = new TreeNode(7);
        TreeNode three = new TreeNode(2);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(6);
        TreeNode six = new TreeNode(8);

        root1.one = one;
        root1.two = two;
        root1.three = three;
        one.one = null;
        one.two = null;
        one.three = null;
        two.one = four;
        two.two = five;
        two.three = null;
        three.one = null;
        three.two = null;
        three.three = null;
        four.one = six;
        four.two = null;
        four.three = null;
        five.one = null;
        five.two = null;
        five.three = null;
        six.one = null;
        six.two = null;
        six.three = null;

        one.parent = root1;
        two.parent = root1;
        three.parent = root1;
        four.parent = two;
        five.parent = two;
        six.parent = four;

        System.out.println("两个节点的最低公共祖先："+p.GetLowestCommonAncestor(root1,six,two));
    }

    private TreeNode GetLowestCommonAncestor(TreeNode root1, TreeNode node1, TreeNode node2) {
        if(root1==null||node1==null||node2==null) return null;
        int depth1=findTheDepthOfTheNode(node1,node2);
        int depth2=findTheDepthOfTheNode(node2,node1);
        if(depth1==-1) return node2.parent;
        if(depth2==-1) return node1.parent;
        TreeNode p=(depth1>depth2?node1:node2);
        TreeNode q=(depth1<depth2?node2:node1);
        int depth=Math.abs(depth1-depth2);
        while(depth>0){
            p=p.parent;
            depth--;
        }
        while(p!=q){
            p=p.parent;
            q=q.parent;
        }
        return p;



    }

    private int findTheDepthOfTheNode(TreeNode node1, TreeNode node2) {
        int depth = 0;
        //从叶子节点向上遍历
        while(node1.parent != null) {
            node1 = node1.parent;
            depth++;
            if(node1 == node2)
                return -1;
        }
        return depth;
    }
}
